We revisit the probabilistic construction of sparse random matrices whereeach column has a fixed number of nonzeros whose row indices are drawnuniformly at random with replacement. These matrices have a one-to-onecorrespondence with the adjacency matrices of fixed left degree expandergraphs. We present formulae for the expected cardinality of the set ofneighbors for these graphs, and present tail bounds on the probability thatthis cardinality will be less than the expected value. Deducible from thesebounds are similar bounds for the expansion of the graph which is of interestin many applications. These bounds are derived through a more detailed analysisof collisions in unions of sets. Key to this analysis is a novel {\em dyadicsplitting} technique. The analysis led to the derivation of better orderconstants that allow for quantitative theorems on existence of losslessexpander graphs and hence the sparse random matrices we consider and alsoquantitative compressed sensing sampling theorems when using sparse nonmean-zero measurement matrices.
展开▼
机译：我们重新研究稀疏随机矩阵的概率构造，其中每列具有固定数量的非零值，其行索引通过替换均匀地随机绘制。这些矩阵与固定左度展开器图的邻接矩阵一一对应。我们为这些图提供了一组邻居的期望基数的公式，并给出了该基数小于期望值的概率的尾限。从这些边界可推导的是图扩展的相似范围，这在许多应用中都令人感兴趣。这些边界是通过对集合并集中的冲突进行更详细的分析得出的。该分析的关键是新颖的{\ em dyadicsicstting}技术。分析导致了更好的阶数常数的推导，这些阶数常数允许对无损展开图的存在进行定量定理，因此可以考虑我们所考虑的稀疏随机矩阵，以及在使用稀疏非均值零度量矩阵时的量化压缩感知采样定理。
展开▼
